package lcr;

public class Test0062 {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("ab");
        System.out.println(trie.search("a"));
        System.out.println(trie.search("ab"));
        System.out.println(trie.startsWith("aba"));
        trie.insert("app");
        System.out.println(trie.search("app"));
    }
}

class Trie {

    private Trie[] tries;
    private boolean isEnd;

    /** Initialize your data structure here. */
    public Trie() {
        this.isEnd=false;
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        insert(word.toCharArray(),0);
    }

    public void insert(char[] word, int index) {
        if (tries == null) tries = new Trie[26];
        Trie trie = tries[word[index] - 'a'];
        if (trie ==null) {
            trie = new Trie();
            tries[word[index]-'a'] = trie;
        }
        if (index == word.length-1) {
            trie.setEnd(true);
        }else {
            trie.insert(word,index+1);
        }
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        return search(word.toCharArray(),0);
    }

    public boolean search(char[] word, int index) {
        if (tries == null) return false;
        Trie trie = tries[word[index] - 'a'];
        if (trie == null) return false;
        if (index == word.length-1) {
            return trie.isEnd();
        }
        return trie.search(word,index+1);
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {

        return startsWith(prefix.toCharArray(),0);
    }

    public boolean startsWith(char[] word,int index) {
        if (tries == null) return false;
        Trie trie = tries[word[index] - 'a'];
        if (trie == null) return false;
        if (index == word.length-1) return true;
        return trie.startsWith(word,index+1);
    }

    public boolean isEnd(){
        return isEnd;
    }
    public void setEnd(boolean isEnd){
        this.isEnd = isEnd;
    }
}
